import java.util.ArrayDeque;
import java.util.Deque;

public class LongestValidParentheses {
    // 最长有效括号
    // https://leetcode.cn/problems/longest-valid-parentheses/
    public int longestValidParentheses(String s) {
        int left = 0, right = 0, maxLength = 0;
        char[] arr = s.toCharArray();
        // 先从左往右遍历一遍字符串，统计最长有效括号的长度
        // 从左往右遍历的匹配规则是右括号匹配左括号
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                // 当遇到左右括号数量相等的话，就说明是有效的括号，记录最大长度
                maxLength = Math.max(maxLength, right * 2);
            } else if (right > left) {
                // 如果右括号的数量大于左括号的数量，那么就是非有效的括号，left、right置为0
                left = right = 0;
            }
        }

        left = right = 0;
        // 从右往左遍历的话就是左括号匹配右括号
        for (int i = arr.length-1; i >= 0; i--) {
            if (arr[i] == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                // 当遇到左右括号数量相等的话，就说明是有效的括号，记录最大长度
                maxLength = Math.max(maxLength, left * 2);
            } else if (left > right) {
                // 如果左括号的数量大于右括号的数量，那么就是非有效的括号，left、right置为0
                left = right = 0;
            }
        }
        return maxLength;
    }

    /**
     * 使用栈解决，栈中存放最近一个未匹配括号的下标
     * @param s
     * @return
     */
    public int longestValidParentheses1(String s) {
        // 栈中存放最后一个未匹配的括号的下标
        Deque<Integer> stack = new ArrayDeque<>();
        stack.add(-1);
        int maxLength = 0;
        char[] arr = s.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == '(') {
                // 因为是右括号匹配左括号，所以当遇到左括号的时候是匹配不了的，直接压栈
                stack.push(i);
            } else {
                // 因为栈中放了一个默认的-1，所以栈中至少会有一个元素，可以先出栈
                stack.pop();
                // 如果栈是空的，说明在这个右括号之前是没有左括号与之匹配的，所以将这个右括号的下标压栈
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    // 如果不为空,说明这个右括号之前是有左括号与之匹配的,所以我们更新最长有效括号的长度
                    // 以当前位置的右括号为结束的最长有效括号的长度就是当前位置-栈顶元素下标
                    maxLength = Math.max(maxLength, i-stack.peek());
                }
            }
        }
        return maxLength;
    }
}
